import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Solution133 {

    static class Node {
        public int val;
        public List<Node> neighbors;
        public Node() {
            val = 0;
            neighbors = new ArrayList<Node>();
        }
        public Node(int _val) {
            val = _val;
            neighbors = new ArrayList<Node>();
        }
        public Node(int _val, ArrayList<Node> _neighbors) {
            val = _val;
            neighbors = _neighbors;
        }
    }

    public Node cloneGraph(Node node) {
        if (node==null){
            return null;
        }
        Map<Integer,Node> map=new HashMap<>();
        int[] visit=new int[105];
        dfs(node,map);
        return dfs2(node,map,visit);
    }

    private Node dfs2(Node node, Map<Integer, Node> map,int[] visit) {
        if (visit[node.val]==1){
            return map.get(node.val);
        }
        visit[node.val]=1;
        Node node1=map.get(node.val);
        List<Node> nodes=new ArrayList<>();
        for (Node neighbor : node.neighbors) {
            nodes.add(map.get(neighbor.val));
        }
        for (Node neighbor : node.neighbors) {
            dfs2(neighbor,map,visit);
        }
        node1.neighbors=nodes;
        return node1;
    }

    private void dfs(Node node, Map<Integer, Node> map) {
        if (!map.containsKey(node.val)){
            map.put(node.val,new Node(node.val));
        }else {
            return;
        }
        for (Node neighbor : node.neighbors) {
            dfs(neighbor,map);
        }
    }

    public static void main(String[] args) {
        Node n1=new Node(1);
        Node n2=new Node(2);
        Node n3=new Node(3);
        Node n4=new Node(4);
        List<Node> l1=new ArrayList<>();
        l1.add(n2);l1.add(n3);l1.add(n4);n1.neighbors=l1;
        List<Node> l2=new ArrayList<>();
        l2.add(n1);l2.add(n3);l2.add(n4);n2.neighbors=l2;
        List<Node> l3=new ArrayList<>();
        l3.add(n2);l3.add(n1);l3.add(n4);n3.neighbors=l3;
        List<Node> l4=new ArrayList<>();
        l4.add(n2);l4.add(n3);l4.add(n1);n4.neighbors=l4;
        Node node=new Solution133().cloneGraph(n1);
        List<Node> list=node.neighbors;
        for (Node node1 : list) {
            System.out.println(node1.val);
        }
    }
}
